let createNode = require('./tools/create-node');
/**
    给你一个链表数组，每个链表都已经按升序排列。
    请你将所有链表合并到一个升序链表中，返回合并后的链表。
    示例 1：

    输入：lists = [[1,4,5],[1,3,4],[2,6]]
    输出：[1,1,2,3,4,4,5,6]
    解释：链表数组如下：
    [
        1->4->5,
        1->3->4,
        2->6
    ]
    将它们合并到一个有序链表中得到。
    1->1->2->3->4->4->5->6
    示例 2：

    输入：lists = []
    输出：[]
    示例 3：

    输入：lists = [[]]
    输出：[]
     

    提示：

    k == lists.length
    0 <= k <= 10^4
    0 <= lists[i].length <= 500
    -10^4 <= lists[i][j] <= 10^4
    lists[i] 按 升序 排列
    lists[i].length 的总和不超过 10^4


 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
// var mergeKLists = function(lists) {
//     if(list.length == 0) {
//         return [];
//     }
//     var mergeTwoLists = function(l1, l2) {
//         if(l1 == null) {
//             return l2;
//         }
//         if(l2 == null) {
//             return l1;
//         }
//         if(l1.val > l2.val) {
//             l2.next = mergeTwoLists(l2.next, l1);
//             return l2;
//         } else {
//             l1.next = mergeTwoLists(l1.next, l2);
//             return l1;
//         }
//     };
//     let result = list[0];
//     for(let i = 1; i < list.length; i++) {
//         result = mergeTwoLists(result, list[i]);
//     }
//     return result;
// };
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
// var mergeKLists2 = function(lists) {
//     let head = {val: 0, next: null};
//     let currentNode = head;
//     while(true){
//         let minIndex = -1;
//         let minNode = null;
//         for(let i = 0; i < lists.length; i++) {
//             if(lists[i] == null) {
//                 continue;
//             }
//             if(minNode == null || minNode.val > lists[i].val) {
//                 minNode = lists[i];
//                 minIndex = i;
//             }
//         }
//         if(minIndex == -1) {
//             break;
//         }
//         currentNode.next = minNode;
//         if(minNode.next == null) {
//             lists.splice(minIndex, 1);
//         } else {
//             lists[minIndex] = minNode.next;
//         }
//         currentNode = minNode;
//         console.log(JSON.stringify(lists));
//     }
//     return head.next;
// };
var mergeTwoLists = function(l1, l2) {
    if(l1 == null && l2 == null) {
        return null;
    }
    let head = {val: 0, next: null}
    let currentNode = head;
    while(l1 != null && l2 != null) {
        if(l1.val > l2.val) {
            currentNode.next = l2;
            l2 = l2.next;
        } else {
            currentNode.next = l1;
            l1 = l1.next;
        }
        currentNode = currentNode.next;
    }
    if(l1 != null) {
        currentNode.next = l1;
    } else {
        currentNode.next = l2;
    }
    return head.next;
    // if(l1 == null) {
    //     return l2;
    // }
    // if(l2 == null) {
    //     return l1;
    // }
    // if(l1.val > l2.val) {
    //     l2.next = mergeTwoLists(l2.next, l1);
    //     return l2;
    // } else {
    //     l1.next = mergeTwoLists(l1.next, l2);
    //     return l1;
    // }
};
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
let mergeKLists = (lists) => {
    if (lists.length <= 1) return lists[0] || null;
    const newLists = [];
    for (let i = 0; i < lists.length; i += 2) {
      newLists.push(mergeTwoLists(lists[i], lists[i + 1] || null));
    }
    return mergeKLists(newLists);
}
function run () {
    let args = [];
    let vals = [[1,2,2],[1,1,2]];
    
    vals.forEach(arr => {
        args.push(createNode.createNode(arr))
    });
    return mergeKLists(args);
}
module.exports = run;